1. Field of the Invention
The present invention relates to a Viterbi decoding apparatus used typically in satellite broadcasting applications.
2. Description of the Prior Art
The Viterbi decoding method is known as one of the methods for decoding convolutional codes. More specifically, the Viterbi decoding method is a maximum likelihood decoding method that addresses convolutional codes. The method permits error correction by selecting the code stream most like the received code stream (called the maximum likelihood path) from among a plurality of code streams that may be generated by the encoder on the transmitting side.
The maximum likelihood path is selected not by comparison between all paths but by first obtaining the Hamming distance between the received code stream and each of all code streams that may be generated by the transmitting side. The maximum likelihood path to be selected is the path for which the accumulated Hamming distances are the smallest (i.e., likelihood is the highest). Once the maximum likelihood path is selected, only those paths that are necessary for decoding (called surviving paths) are examined in principle. If the path length is long enough, the tips (i.e., roots) of the surviving paths coincide with one another. That is, retrogressing to the root of any surviving path means eventually decoding the same value. Thus the correct word is decoded by examining the path length that is not so long as to raise the error rate of decoding and by retrogressing over that length up to that point in time whose data are taken as the target word.
FIG. 6 is a block diagram of a typical prior art Viterbi decoding apparatus operating on the above-described principle. The Viterbi decoding apparatus of FIG. 6 comprises a branch metric calculating circuit 101, an ACS circuit 102, a normalizing circuit 103, a state metric storing circuit 104, a path memory circuit 105 and a maximum likelihood path determining circuit 106. Upon receipt of data (input data) from the transmitting side, the apparatus selects the code stream most like the received code stream (called the maximum likelihood path) from among a plurality of code streams that may be generated by the encoder on the transmitting side. The apparatus then generates decoded data based on the selected code stream.
Given the input data, the branch metric calculating circuit 101 calculates the branch metric of the data and supplies the result of the calculation (i.e., branch metric) to the ACS circuit 102.
In addition to the branch metric from the branch metric calculating circuit 101, the ACS circuit 102 also receives a state metric (cumulative sum) coming from the state metric storing circuit 104. Based on these inputs and for every two paths converging on a certain state, the ACS circuit 102 adds the Hamming distance (branch metric) between the received code and each path and the cumulative sum (state metric) of past branch metrics for the path. The sums are compared between the two paths. The more likely path of the two is selected according to the result of the comparison. The result of the selection is fed to the path memory circuit 105, and the newly obtained cumulative sum (state metric) is supplied to the normalizing circuit 103.
If the constraint length for the above setup is 3, what happens is as follows: As shown in the transition diagram of FIG. 7, for every two paths converging on a certain state, the Hamming distance (branch metric) between the received code and each path and the cumulative sum (state metric) of past branch metrics for that path are added. The sums are compared between the two paths. The more likely path of the two is selected on the basis of the result of the comparison.
The normalizing circuit 103 normalizes the state metric output by the ACS circuit 102, bringing the state metric into a predetermined range. The normalized state metric is supplied to the state metric storing circuit 104.
On receiving the normalized state metric from the normalizing circuit 103, the state metric storing circuit 104 stores the state metric and feeds it back to the ACS circuit 102.
The path memory circuit 105 comprises a plurality of path memory cells 11011 through 1104n arranged in matrix fashion, as depicted in FIG. 8. Based on selection signals PS.sub.1 through PS.sub.4 from the ACS circuit 102, selecting circuits 111 select the input data. The result of the selection is temporarily retained by D-flip-flops 112 in synchronism with a clock signal CLK. In this manner, as shown in FIG. 9, the result of the selection from the ACS circuit 102 is stored and then forwarded to the maximum likelihood path determining circuit 106.
In turn, the maximum likelihood path determining circuit 106 determines the maximum likelihood path based on the result of the selection stored in the path memory circuit 105, as illustrated in FIG. 10. The circuit 106 then generates decoded data for output.
In the prior art Viterbi decoding apparatus described above, the state metric value from the preceding decoding process is added to that from the current decoding process through a loop made of parts ranging from the state metric storing circuit 104 to an adder, not shown, in the ACS circuit 102.
The operations inside the loop must be executed under a predetermined information rate. To raise the information rate requires minimizing the upper limit of the time it takes to pass through the loop.
The component that most affects the operation speed within this loop is the ACS circuit 102. This is because the ACS circuit 102, for every two paths converging on a certain state, adds the Hamming distance (branch metric) between the received code and each path and the cumulative sum (state metric) of past branch metrics for the path. The ACS circuit 102 then compares the sums between the two paths, and the more likely path thereof is selected according to the result of the comparison.
The prior art ACS circuit 102 for use in the above Viterbi decoding apparatus takes time T.sub.T when outputting the path selection signal that serves as path transition information for each time slot, as shown in FIG. 7. The time T.sub.T is given by the expression below. EQU T.sub.T =T.sub.A +T.sub.C +T.sub.S ( 1)
where, TA is the time for addition, T.sub.C is the time for comparison and T.sub.S is the time for selection.
At the same time, the increase in the information rate requires more strict accuracy of clock synchronization. This means that raising the information rate with the conventional circuit configuration kept unmodified can lead to various circuit operation problems. One such problem is an inappropriately shifted transition time. Another problem is the difficulty of clock control.
Furthermore, in the conventional setup, the upper limit of the operation speed is determined by the processing speed of the loop per time slot. If the constraint length is 7 and the coding rate is 7/8, the maximum operation speed is 25 Mbps in the current state of the art.
The constraint above makes it impossible to process large quantities of information amounting to as much as 30 Mbps, the mass of information being characteristic of high-definition television applications involving the decoding of convolutional codes.